package com.tongtech.proxy.core.protocol;

public class brTanselete<T extends Comparable<T>> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node<T> root;

    public void insert(T data) {
        Node<T> newNode = new Node<>(data);
        insert(newNode);
    }

    private void insert(Node<T> newNode) {
        if (root == null) {
            root = newNode;
        } else {
            insertNode(newNode, root);
        }
        newNode.color = RED;
        fixInsert(newNode);
    }

    private void insertNode(Node<T> newNode, Node<T> currentNode) {
        if (newNode.data.compareTo(currentNode.data) < 0) {
            if (currentNode.left == null) {
                currentNode.left = newNode;
                newNode.parent = currentNode;
            } else {
                insertNode(newNode, currentNode.left);
            }
        } else {
            if (currentNode.right == null) {
                currentNode.right = newNode;
                newNode.parent = currentNode;
            } else {
                insertNode(newNode, currentNode.right);
            }
        }
    }

    private void fixInsert(Node<T> newNode) {
        while (newNode != root && newNode.parent.color == RED) {
            if (newNode.parent == newNode.parent.parent.left) {
                Node<T> uncle = newNode.parent.parent.right;
                if (uncle != null && uncle.color == RED) {
                    newNode.parent.color = BLACK;
                    uncle.color = BLACK;
                    newNode.parent.parent.color = RED;
                    newNode = newNode.parent.parent;
                } else {
                    if (newNode == newNode.parent.right) {
                        newNode = newNode.parent;
                        leftRotate(newNode);
                    }
                    newNode.parent.color = BLACK;
                    newNode.parent.parent.color = RED;
                    rightRotate(newNode.parent.parent);
                }
            } else {
                Node<T> uncle = newNode.parent.parent.left;
                if (uncle != null && uncle.color == RED) {
                    newNode.parent.color = BLACK;
                    uncle.color = BLACK;
                    newNode.parent.parent.color = RED;
                    newNode = newNode.parent.parent;
                } else {
                    if (newNode == newNode.parent.left) {
                        newNode = newNode.parent;
                        rightRotate(newNode);
                    }
                    newNode.parent.color = BLACK;
                    newNode.parent.parent.color = RED;
                    leftRotate(newNode.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }

    private void leftRotate(Node<T> node) {
        Node<T> rightChild = node.right;
        node.right = rightChild.left;
        if (rightChild.left != null) {
            rightChild.left.parent = node;
        }
        rightChild.parent = node.parent;
        if (node.parent == null) {
            root = rightChild;
        } else if (node == node.parent.left) {
            node.parent.left = rightChild;
        } else {
            node.parent.right = rightChild;
        }
        rightChild.left = node;
        node.parent = rightChild;
    }

    private void rightRotate(Node<T> node) {
        Node<T> leftChild = node.left;
        node.left = leftChild.right;
        if (leftChild.right != null) {
            leftChild.right.parent = node;
        }
        leftChild.parent = node.parent;
        if (node.parent == null) {
            root = leftChild;
        } else if (node == node.parent.left) {
            node.parent.left = leftChild;
        } else {
            node.parent.right = leftChild;
        }
        leftChild.right = node;
        node.parent = leftChild;
    }

    public static void main(String[] args) {
        brTanselete<Integer> tree = new brTanselete<>();
        tree.insert(15);
        tree.insert(10);
        tree.insert(20);
        tree.insert(5);
        tree.insert(12);
        tree.insert(10); // 插入重复的元素

        System.out.println("中序遍历：");
        tree.inOrderTraversal();
    }

    private void inOrderTraversal() {
        inOrderTraversal(root);
    }

    private void inOrderTraversal(Node<T> node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.print(node.data + " ");
            inOrderTraversal(node.right);
        }
    }

    private static class Node<T> {
        T data;
        boolean color;
        Node<T> parent;
        Node<T> left;
        Node<T> right;

        public Node(T data) {
            this.data = data;
            this.color = RED;
            this.parent = null;
            this.left = null;
            this.right = null;
        }
    }
}
